package de.h_da.fbi.cg.pointcloud.emst;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

import de.h_da.fbi.cg.pointcloud.adt.Edge;
import de.h_da.fbi.cg.pointcloud.adt.Graph;
import de.h_da.fbi.cg.pointcloud.adt.Vertex;
import de.h_da.fbi.cg.pointcloud.util.Quicksort;
import de.h_da.fbi.cg.pointcloud.util.UniqueArrayList;

/**
 * @author Nicolas Gramlich
 * @since 10:22:23 - 11.11.2010
 */
public class BoruvkaEuclideanMinimumSpanningTreeAlgorithm implements IEuclideanMinimumSpanningTreeAlgorithm {
	// ===========================================================
	// Constants
	// ===========================================================

	// ===========================================================
	// Fields
	// ===========================================================

	private final ExecutorService mExecutorService;

	// ===========================================================
	// Constructors
	// ===========================================================

	public BoruvkaEuclideanMinimumSpanningTreeAlgorithm() {
		this.mExecutorService = Executors.newFixedThreadPool(8);
//		this.mExecutorService = Executors.newCachedThreadPool();
	}

	// ===========================================================
	// Getter & Setter
	// ===========================================================

	// ===========================================================
	// Methods for/from SuperClass/Interfaces
	// ===========================================================

	@Override
	public Graph computeEuclideanMinimumSpanningTree(final Graph pGraph) {
		final ArrayList<Graph> components = this.initComponents(pGraph.getVertices(), pGraph.getEdges());
		return this.computeEuclideanMinimumSpanningTree(components);
	}

	@Override
	public Graph computeEuclideanMinimumSpanningTree(final ArrayList<Graph> pComponents) {
		while(pComponents.size() > 1) {
			final ArrayList<Edge> shortestInterComponentEdges = this.getShortestInterComponentEdges(pComponents);

			Quicksort.sort(shortestInterComponentEdges);

			this.connectComponents(pComponents, shortestInterComponentEdges);
		}

		return pComponents.get(0);
	}

	// ===========================================================
	// Methods
	// ===========================================================

	private void connectComponents(final ArrayList<Graph> pComponents, final ArrayList<Edge> pShortestInterComponentEdges) {
		final HashSet<Graph> componentsTouched = new HashSet<Graph>();
		final ArrayList<Edge> independantComponentConnectionEdges = new ArrayList<Edge>();

		for(int i = pShortestInterComponentEdges.size() - 1; i >= 0; i--) {
			final Edge shortestInterComponentEdge = pShortestInterComponentEdges.get(i);
			final Graph componentA = shortestInterComponentEdge.mVertexA.mGraph;
			final Graph componentB = shortestInterComponentEdge.mVertexB.mGraph;

			if(!componentsTouched.contains(componentA) && !componentsTouched.contains(componentB)) {
				independantComponentConnectionEdges.add(pShortestInterComponentEdges.remove(i));

				componentsTouched.add(componentA);
				componentsTouched.add(componentB);
			}
		}

		/* Run in parallel where we determined it is possible. */
		final List<Callable<Graph>> tasks = new ArrayList<Callable<Graph>>();
		for(int i = independantComponentConnectionEdges.size() - 1; i >= 0; i--) {
			tasks.add(new ShortestInterComponentEdgeUnionCallable(independantComponentConnectionEdges.get(i)));
		}

		try {
			final List<Future<Graph>> results = this.mExecutorService.invokeAll(tasks);
			for(final Future<Graph> futureGraph : results) {
				try {
					pComponents.remove(futureGraph.get());
				} catch (final ExecutionException e) {
					e.printStackTrace();
				}
			}
		} catch (final InterruptedException e) {
			e.printStackTrace();
		}

		/* Do the rest of the components sequential. */
		for(int i = pShortestInterComponentEdges.size() - 1; i >= 0; i--) {
			final Edge shortestInterComponentEdge = pShortestInterComponentEdges.get(i);
			if(shortestInterComponentEdge.isInterComponentEdge()) {
				final Graph componentA = shortestInterComponentEdge.mVertexA.mGraph;
				final Graph componentB = shortestInterComponentEdge.mVertexB.mGraph;

				shortestInterComponentEdge.mEuclideanMinumumSpanningTreeEdge = true;

				pComponents.remove(componentB);
				/* Connect components. */
				componentA.union(componentB);
			}
		}
		
//		for(int i = pShortestInterComponentEdges.size() - 1; i >= 0; i--) {
//			final Edge shortestInterComponentEdge = pShortestInterComponentEdges.get(i);
//			if(shortestInterComponentEdge.isInterComponentEdge()) {
//				shortestInterComponentEdge.mEuclideanMinumumSpanningTreeEdge = true;
//
//				pComponents.remove(shortestInterComponentEdge.mVertexB.mGraph);
//				/* Connect components. */
//				shortestInterComponentEdge.mVertexA.mGraph.union(shortestInterComponentEdge.mVertexB.mGraph);
//			}
//		}
	}

	private ArrayList<Graph> initComponents(final ArrayList<Vertex> pVertices, final ArrayList<Edge> pEdges) {
		final ArrayList<Graph> components = new ArrayList<Graph>();

		final List<Callable<Graph>> tasks = new ArrayList<Callable<Graph>>();
		for(int i = pVertices.size() - 1; i >= 0; i--) {
			tasks.add(new InitComponentCallable(pVertices.get(i), pEdges));
		}

		try {
			final List<Future<Graph>> results = this.mExecutorService.invokeAll(tasks);
			for(final Future<Graph> futureGraph : results) {
				try {
					components.add(futureGraph.get());
				} catch (final ExecutionException e) {
					e.printStackTrace();
				}
			}
		} catch (final InterruptedException e) {
			e.printStackTrace();
		}

		//		for(int i = pVertices.size() - 1; i >= 0; i--) {
		//			final Vertex vertex = pVertices.get(i);
		//
		//			final Graph component = new Graph();
		//			components.add(component);
		//			component.addVertex(vertex);
		//
		//			/* Add all edges the vertex is part of. */
		//			BoruvkaEuclideanMinimumSpanningTreeAlgorithm.addAllEdgesThatContainVertex(component, vertex, pEdges);
		//		}

		return components;
	}

	private static void addAllEdgesThatContainVertex(final Graph pGraph, final Vertex pVertex, final ArrayList<Edge> pEdges) {
		for(int i = pEdges.size() - 1; i >= 0; i--) {
			final Edge edge = pEdges.get(i);
			if(edge.contains(pVertex)) {
				pGraph.addEdge(edge);
			}
		}
	}

	private UniqueArrayList<Edge> getShortestInterComponentEdges(final ArrayList<Graph> pGraphs) {
		final UniqueArrayList<Edge> shortestOutgoingEdges = new UniqueArrayList<Edge>();

		final List<Callable<Edge>> tasks = new ArrayList<Callable<Edge>>();
		for(int i = pGraphs.size() - 1; i >= 0; i--) {
			tasks.add(new GetShortestEdgeRunnable(pGraphs.get(i)));
		}

		try {
			final List<Future<Edge>> results = this.mExecutorService.invokeAll(tasks);
			for(final Future<Edge> futureEdge : results) {
				try {
					shortestOutgoingEdges.add(futureEdge.get());
				} catch (final ExecutionException e) {
					e.printStackTrace();
				}
			}
		} catch (final InterruptedException e) {
			e.printStackTrace();
		}

		//		for(int i = pGraphs.size() - 1; i >= 0; i--) {
		//			final Graph graph = pGraphs.get(i);
		//			final Edge shortestOutgoingEdge = graph.getShortestOutgoingEdge();
		//			shortestOutgoingEdges.add(shortestOutgoingEdge);
		//		}

		return shortestOutgoingEdges;
	}

	// ===========================================================
	// Inner and Anonymous Classes
	// ===========================================================

	private static class ShortestInterComponentEdgeUnionCallable implements Callable<Graph> {
		private final Edge mShortestInterComponentEdge;

		public ShortestInterComponentEdgeUnionCallable(final Edge pShortestInterComponentEdge) {
			this.mShortestInterComponentEdge = pShortestInterComponentEdge;
		}

		@Override
		public Graph call() throws Exception {
			final Graph componentA = this.mShortestInterComponentEdge.mVertexA.mGraph;
			final Graph componentB = this.mShortestInterComponentEdge.mVertexB.mGraph;

			this.mShortestInterComponentEdge.mEuclideanMinumumSpanningTreeEdge = true;

			/* Connect components. */
			componentA.union(componentB);

			return componentB;
		}
	}

	private static class InitComponentCallable implements Callable<Graph> {
		private final Vertex mVertex;
		private final ArrayList<Edge> mEdges;

		public InitComponentCallable(final Vertex pVertex, final ArrayList<Edge> pEdges) {
			this.mVertex = pVertex;
			this.mEdges = pEdges;
		}

		@Override
		public Graph call() throws Exception {
			final Graph component = new Graph();
			component.addVertex(this.mVertex);
			BoruvkaEuclideanMinimumSpanningTreeAlgorithm.addAllEdgesThatContainVertex(component, this.mVertex, this.mEdges);

			return component;
		}
	}

	private static class GetShortestEdgeRunnable implements Callable<Edge> {
		private final Graph mGraph;

		public GetShortestEdgeRunnable(final Graph pGraph) {
			this.mGraph = pGraph;
		}

		@Override
		public Edge call() throws Exception {
			return this.mGraph.getShortestOutgoingEdge();
		}
	}
}
